1. Field of the Invention
The present invention relates to an integer permutation method and an integer permutation system for permuting a data sequence in the magnitude order of data.
2. Related Art
A method called radix sort is known as sort processing for permuting data in the magnitude order (permutation processing). Here, the radix sort method will be discussed by taking integer permutation of 3-digit integer data as an example with reference to FIG. 6. First, as shown in FIG. 6(a), the integer data to be sorted is disassembled into elements at hundreds, tens, and units. Next, attention is focused on the units and the data is permuted so that the values of the elements at the units are arranged in the ascending magnitude order, as shown in FIG. 6(b). For the data sequence after the permutation is executed, then the data is permuted so that the values of the elements at the tens are arranged in the ascending magnitude order, as shown in FIG. 6(c). Last, the data is permuted so that the values of the elements at the hundreds are arranged in the ascending magnitude order, as shown in FIG. 6(d). Integer permutation for each digit place is executed in sequence from the low-order place to the high-order place, thereby finally providing an integer data sequence resulting from integer permutation in the ascending magnitude order of the integer data.
To execute the radix sort method by hardware, generally two buffers (first and second buffers) are used as described below:
First, the integer data sequence to be sorted is once stored in the first buffer. The integer data in the first buffer is read in sequence and written into storage areas in the second buffer. The storage areas into which the integer data is written are determined based on the values of the elements at units of the integer data. That is, the integer data is distributed in sequence to the storage areas in the second buffer in such a manner that the integer data whose element at units is 0 is written into the top storage area in the second buffer, that the integer data whose element at units is 1 is written into the next storage area, . . . , and that the integer data whose element at units is 9 is written into the last storage area. As a result of the processing, an integer data sequence undergoing integer permutation at units is provided in the second buffer.
Next, the integer data is read in sequence starting at the top storage area in the second buffer and written into the storage areas in the first buffer. In this case, the storage areas into which the integer data is written are determined based on the values of the elements at tens of the integer data. After the processing is performed, an integer data sequence undergoing integer permutation at tens is provided in the first buffer. Last, the integer data is read in sequence starting at the top storage area in the first buffer and written into the storage areas in the second buffer corresponding to the values of the elements at hundreds of the integer data. An integer data sequence undergoing integer permutation is now provided in the second buffer.
However, if such a method is adopted, storage areas into which all integer data pieces can be written for each element need to be provided because the values of the elements of all integer data can equal in the worst case. Therefore, assuming that the number of integer data pieces is N, that the number of elements making up each integer data piece is M, and that the number of types of values that each element can take is P, the number of storage areas required in the first and second buffers is N.times.P (=N.times.P.times.Mlog.sub.2 P bits). Thus, if the conventional integer permutation method is attempted to be executed by hardware, buffers of extremely large capacities become necessary depending on the integer permutation processing contents.